Data are typically encoded before transmission to a receiver or to a storage device, to protect the data from errors which may result from a noisy communications channel or a defect in the storage medium. An encoder manipulates data symbols in accordance with an error correction code and produces error correction symbols. If the error correction code is systematic, the encoder forms a code word by appending the error correction symbols to the applicable data symbols. If the error correction code is non-systematic, the encoder forms the code word using only the error correction symbols. In either case, the code word is transmitted or stored. When the code word is later received or retrieved it is decoded to reproduce the data symbols, and errors in the data symbols are corrected, if possible, using the error correction symbols.
One error correction code that is particularly well suited to the correction of multiple errors is a non-systematic convolutional code. An encoder encoding data in accordance with an (n,k,m) convolutional code produces for k data symbols an n-symbol code word, which is a rate k/n code. The n-symbol code word is based on the k data symbols and, also, on m previously encoded data symbols, where m is called the "memory order" of the encoder. The convolutional encoder thus includes m stages of memory, for example, m one-symbol shift registers, and the contents of the m registers at the time when the k data symbols are applied to the encoder affect in a predetermined manner the code word generated by the encoder.
The m shift registers are updated each time the encoder produces a code word. The m registers are essentially a finite state machine which changes state based on the data applied to the encoder. In an encoder of interest, one data symbol (k=1) is encoded using a binary code to produce a two-symbol code word (n=2) and the registers change state by including in a first register the data symbol and shifting the contents of the remaining registers. The data thus affects the encoding of m+1 code words since the data remains in the registers until they have shifted m times. The code has a "constraint length" of K=m+1.
One method of decoding code words encoded using an (n,k,m) convolutional code is commonly referred to as maximum likelihood decoding. This type of decoding, in essence, involves finding for a stream of received or retrieved code words a most likely stream of error free code words, and then, determining for these error free code words the associated data symbols. Maximum likelihood decoding works particularly well with code words of non-systematic convolutional codes.
One kind of maximum likelihood decoder is commonly referred to as a Viterbi decoder. Conceptually, a Viterbi decoder uses a decoding trellis, which has a branch for each possible code word and connected paths of branches for each possible stream, or sequence, of code words. The decoder essentially finds a path through the trellis which is "closest" to, or most like, the received stream of code words. It then treats the code words on this "most likely" trellis path as the received code words and assigns data values to them, to produce a best estimate of the transmitted data.
To determine the most likely path, the decoder calculates, for each received code word, a set of branch metrics. A branch metric is a numerical representation of the likelihood that the transmitted code word, which may contain errors on reception, is actually the code word which corresponds to a particular branch. In one such decoder the branch metrics are the Hamming distances between the received code word and the code words associated with the various branches.
FIG. 1 depicts a decoding trellis for a rate 1/2 code as discussed above. The code generates for each data symbol (k=1) a two-symbol code word (n=2). The memory order of the code is two (m=2), and thus an associated encoder includes two shift registers. The code is binary, and each symbol is one bit in length. The possible code words are represented in the decoding trellis by branches, for example, branches labeled 2-5. The branches depicted as solid lines represent code words associated with a data ZERO and the dashed lines represent code words associated with a data ONE.
Each branch in the decoding trellis leads from an initial state, which represents the state that the m registers are in prior to the formulation of the code word associated with the branch, and leads to an end state, which represents the state that the m registers are in after the formulation of the code word. Thus branch 2 represents a code word 00 produced by the encoding of a ZERO data bit with the registers in state 00. The branch leads from state 00 to state 00. Branch 3 represents a code word 11 produced by the encoding of a ONE data bit with the registers in state 00. The branch leads from the initial register state 00 to an end state 01. The initial state associated with a branch is considered in a decoding level which precedes the decoding level of the end state.
For a binary code there are 2.sup.K-1, or 2.sup.m, possible states associated with each decoding level, where K is the constraint length of the code. In the example, the code has a constraint length of 3, i.e., there are 2 registers, and there are thus 2.sup.2 possible register states, namely, 00, 01, 10, 11, in each decoding level. Since the code is a rate 1/n code, i.e. k=1, there are two possible branches leading from each initial state, namely a branch associated with a ZERO data bit and a branch associated with a ONE data bit. Each of these branches necessarily leads to a different end state. Thus for each of the 2.sup.K-1 states in a given decoding level, there are two branches leading to each of these states, and each branch may represent the transmitted code word. Accordingly, to decode the code word the decoder must determine two branch metrics for each of the 2.sup.K-1 possible end states, or a total of 2(2.sup.K-1) branch metrics.
Once the decoder calculates these branch metrics, it next determines the metrics of the various paths leading to the end states. Accordingly, the decoder adds to the branch metrics the appropriate path metrics, which are the sums of the branches leading to the initial states. The decoder then selects a most likely path leading to each of the end states and stores for later use the path metrics and information which identifies these most likely paths. These most likely paths which are also referred to as the "surviving paths." The decoder does not retain information relating to the less likely, or non-surviving, paths. In this way, the decoder "prunes" these paths from the trellis, and thereby eliminates for a next level of decoding a portion of the path metric calculations.
When a sufficient number of code words have been included in the trellis paths, the most likely code word path is chosen from the surviving paths associated with the end states. The decoder selects as the most likely path the code word path which is "closest" to the received data, i.e., the path with the smallest Hamming distance metric. The decoder then decodes the code words on the most likely path, or "traces back" along the path, to determine the associated data bits.
Prior decoders perform, for each of the 2.sup.K-1 possible end states, 2.sup.k branch metric calculations, one for each branch leading to the state; 2.sup.k path metric access operations, to retrieve previously calculated path metrics; 2.sup.k addition operations, to add the branch metrics to the retrieved path metrics; a surviving path selection operation; a surviving path identifier storage operation; and a path metric storage operation. Each of the branch metric calculations is typically time consuming and/or requires a relatively large look-up table. Also, each of the storage operations typically requires a relatively large memory, since for each state, at a minimum, the memory must hold (i) the branch metrics associated with each branch, (ii) information which identifies the surviving paths, (iii) the surviving path metrics and (iv) the data values associated with the branches on each of the surviving paths must be stored.